<!doctype html public "-//w3c//dtd html 4.0 transitional//en">
<html>

<head>
   <meta http-equiv="Content-Type" content="text/html; charset=iso-8859-1">
   <meta name="Author" content="Hagen Boehm, Dirk W. Jacob">
   <title>SSF Implementation of OSPFv2 v0.2.2</title>
</head>

<body bgcolor="white">

<h2>SSF Implementation of OSPFv2 v0.2.2</h2>

<hr width="100%">
<b><font size="+1"><i>Contents</i></font></b>
<dl>
<dt><a href="#intro">Introduction</a>
<dt><a href="#config">Configuration</a>
<dt><a href="#compliance">Future Work</a>
<dt><a href="#src">Source Code</a>
<dt><a href="#validation">Validation</a>
<dt><a href="#references">References</a>
<dt><a href="#about">Authors</a>
</dl>
<hr width="100%">

<a name="intro"></a>
<h3>Introduction</h3>

<p align="justify">
The Open Shortest Path First (OSPF) protocol is an IP link-state
routing protocol, recommended for distributing routing information
among the routers in a single autonomous system (AS), with explicit
support for classless inter-domain routing (CIDR) address allocation.
</p>

<p align="justify">
SSF.OS.OSPFv2 v0.2.2 is a partial implementation of OSPFv2, based on the Internet
Engineering Task Force's Request for Comments number 2328 "OSPF Version 2" (RFC
2328 <a href="#ref1">[1]</a>). In comparison with SSF.OS.OSPF v0.1.7 it is a thorough 
revision and <b>not</b> compatible to the static version! Completely reimplemented from 
the bottom-up it currently provides an OSPFv2 implementation for point-to-point networks 
<b>only</b>. Starting from basic components like the <i>Hello Protocol</i>, it traverses
a complete state machine, thereby executing the <i>Database Exchange Process</i>, 
<i>Flooding Procedure</i> and <i>Dijkstra's Shortest Path Algorithm</i> until it finally
computes a Routing Table and installs <i>Route Updates</i> in the IP forwarding table. 
Since version 0.2.0 there is support for <i>inter-area routing</i>, but 
<i>route summarization</i> and <i>import/export of external routes</i> are not yet implemented. 
The current OSPFv2 v0.2.2 supports the following LSA types:
<ul>
<li><b>Router LSA (type 1)</b> <i>originated by all routers</i>. It describes
the collected states of the router's interfaces to an area and it is flooded 
throughout a single area only.</li>
<li><b>Summary LSA (type 3)</b> <i>originated by area border routers</i>. It
describes a route to a <b>network</b> destination outside the area, yet still 
inside the AS and it is flooded throughout the LSA's associated area.</li>
<li><b>Summary LSA (type 4)</b> <i>originated by area border routers</i>. It
describes a route to a an <b>AS boundary router</b> destination outside the area, 
yet still inside the AS and it is flooded throughout the LSA's associated area. 
<b> It is neither installed in nor flooded throughout a stub area!</b></li>
</ul>
These LSAs are stored in <i>Link State Databases</i>. There is one database for 
each area the router is attached to. The following fields have been omitted when 
implementing the <i>LSAs</i>:

<ul>
<li><b>LS checksum</b></li>
<li><b>length</b></li>
<li><b>the TOS-fields</b></li>
</ul>

SSFNets limited support of link-layer technologies limits the interactions of
OSPFv2 with the link-layer. Therefore version 0.2.2 only implements a raw framework 
of the OSPF <i>interface state machine</i>. There is <b>no</b> interaction with
a link layer protocol at this time.
</p>

<p align="justify">
Although SSFNet OSPFv2 v0.2.2 is not a complete implementation of all the protocols
capabilities and features (e.g. most of the broadcast media part was omitted) 
described in RFC 2328 <a href="#ref1">[1]</a>, it is much more dynamic than sOSPF 
(SSF.OS.OSPF v0.1.7). You may configure the most <i>Configurable Constants</i> described 
in the RFC. Almost all of the attributes influence the functional behavior of OSPFv2 (see 
<a href="#config">Configuration</a> for details of how to configure an OSPFv2 session). 
Only the debug switches, and the <i>priority</i> attribute, which is used to determine
who becomes a Designated Router in broadcast networks, currently do not influence the
behavior of OSPF, just the output. The latter attribute will be used in the future 
when SSFNet provides multicast/broadcast on broadcast networks. It is planned to extend
the  implementation in a step-by-step fashion. 
</p>

<p align="justify">
After the start, an OSPFv2 session begins with periodically sending <i>Hellos</i>
across the configured interfaces. To add more realistic dynamic behavior, the start
of the <i>Hello Protocol</i> on each router interface is delayed by a random amount
of time between 0 and 10 seconds (all random numbers like start time of Hello Protocol,
database description sequence numbers, etc. are generated by an 
SSF.Util.Random.RandomStream). <br>
When a new neighbor is discovered, the <i>Database Exchange Process</i> synchronizes 
the routers <i>Link State Databases</i> according to RFC 2328 <a href="#ref1">[1]</a>. 
Each router maintains a separate <i>Link State Database</i> for each <i>area</i> it 
is attached to. During and following the link state database exchange the dynamic 
<i>Flooding Procedure</i> announces new information or removes old information throughout 
the net. Thereby routing information is distributed within an area as well as between 
areas. Thus version 0.2.2 supports both <i>int<b>ra</b></i> and <i>int<b>er</b> area 
routing</i>. <br><br>

<b>Inter area routing</b> is <b>limited</b> by the lack of configuring 
<i>address ranges</i>. That means that there is <b>no</b> route aggregation at the 
area border routers which could reduce the size of the databases a lot. The current 
release forces the area border routers to create a summary LSA for each reachable 
network within an area and flood it throughout all the other areas. <br>

Since version 0.2.0 it is possible to configure an area as <i>stub</i>. At area border
routers(<b>!</b>) it is also possible to specify a <i>stub_default_cost</i> attribute
for this area. If the value is greater than 0, the router will announce a 
<i>Default Summary LSA</i> into the stub area. The stub area will base its routing to
AS external destinations solely on this route information, if AS external routes are
supported in one of the future releases of OSPFv2. <br>

OSPFv2 v0.2.2 is as well able to distribute routes to <i>AS Boundary Routers</i>
throughout the net. AS Boundary Routers can not be configured. Instead they are
determined by OSPFv2 itself. A router is supposed to be an AS Boundary Router if it runs
a <a href="../../BGP4/doc/index.html">BGP4</a> session which has a BGP4 neighbor,
configured in an other AS. Be aware that OSPFv2 does not assign type <i>AS Boundary</i>
to routers placed in stub areas! An AS Boundary Router can not be placed in stub
areas according to RFC 2328 <a href="#ref1">[1]</a> chapter 3.6 "Supporting stub areas".

</p>

<p align="justify">
Using <i>Dijkstra's Shortest Path Algorithm</i> a <i>Shortest Path Tree</i> is built 
for each area based on the areas link state database. These trees are used to derive the 
OSPFv2 <i>Routing Table</i>. The table consists of two kinds of entries:

<ul>
<li><b>Network Entry</b> a data structure describing the set of shortest paths leading 
to a network destination, therefore storing the following fields: <br>

<table align="center" border="1" width="100%">
<tr>
<td align="left" valign="center">
<b>area</b>
</td>
<td align="left" valign="center">
indicates the area whose link state information has led to the routing table entry's 
collection of paths. Only one area is associated with a network entry (the one providing
the preferred routes).
</td>
</tr>
<tr>
<td align="left" valign="center">
<b>pathType</b>
</td>
<td align="left" valign="center">
OSPFv2 v0.2.2 knows two path types: <i>intra-area</i> and <i>inter-area</i>.
</td>
</tr>
<tr>
<td align="left" valign="center">
<b>cost</b>
</td>
<td align="left" valign="center">
The link state cost of the path to the destination.
</td>
</tr>
<tr>
<td align="left" valign="center">
<b>type2Cost</b>
</td>
<td align="left" valign="center">
In case of pathType <i>type-2-external</i> it indicates the cost of the path's external 
portion. The current version does not support external paths, so this field is unused.
</td>
</tr>
<tr>
<td align="left" valign="center">
<b>lsOrigin</b>
</td>
<td align="left" valign="center">
The Link State Origin field is not used by the OSPF protocol.
</td>
</tr>
<tr>
<td align="left" valign="center">
<b>equalCostPaths</b>
</td>
<td align="left" valign="center">
A data structure storing <i>Shortest Path Objects</i>. Each of these Objects describes a
shortest path to the destination.
</td>
</tr>
</table>
</li><br>

<li><b>Router Entry</b> a data structure describing the set of shortest paths leading 
to a router destination (v0.2.2 supports area border as well as AS boundary router 
destinations). The following fields are stored here: <br>

<table align="center" border="1" width="100%">
<tr>
<td align="left" valign="center">
<b>optCap</b>
</td>
<td align="left" valign="center">
Boolean array describing the optional capabilities supported by the destination router.
</td>
</tr>
<tr>
<td align="left" valign="center">
<b>pathType</b>
</td>
<td align="left" valign="center">
OSPFv2 v0.2.2 knows two path types: <i>intra-area</i> and <i>inter-area</i>.
</td>
</tr>
<tr>
<td align="left" valign="center">
<b>cost</b>
</td>
<td align="left" valign="center">
The link state cost of the path to the destination.
</td>
</tr>
<tr>
<td align="left" valign="center">
<b>lsOrigin</b>
</td>
<td align="left" valign="center">
The Link State Origin field is not used by the OSPF protocol.
</td>
</tr>
<tr>
<td align="left" valign="center">
<b>isASBoundary</b>
</td>
<td align="left" valign="center">
Boolean value, indicating whether the destination router is an ASBR or not.
</td>
</tr>
<tr>
<td align="left" valign="center">
<b>equalCostPaths</b>
</td>
<td align="left" valign="center">
A data structure storing <i>Shortest Path Objects</i>. Each of these Objects describes a
shortest path to the destination.
</td>
</tr>
</table>
</li>
</ul>
</p>

<p align="justify">
Unlike network entries there may be more than one router entry for the same destination
router. These entries then are distinguished by there associated area ids. <br>
The <i>OSPFv2 Routing Table</i> is a separated data structure. Unlike in real routers, it
is not merged with the <i>IP Forwarding Table</i> but it updates IP with the appropriate
information. An OSPFv2 router thus maintains routes for all reachable
</p>

<ul>
<li><b>stub networks within the AS</b> (only point-to-point!)</li>
<li><b>area border routers in the attached areas</b></li>
<li><b>AS boundary routers in the AS in case the router is not placed in a stub area</b>
</ul>
  
<p align="justify">
Since version 0.2.1 shortest path trees are not anymore build immediately after a topology 
change has been observed. To reduce redundant calculations, OSPFv2 now schedules a
Routing Table calculation when there is no in progress or already scheduled. That is,
when a topology change occurs for the first time after the last Routing Table calculation,
a new calculation is set to be executed <b>5 seconds</b> later from there on. This is
done in the hope that several topology updates may be bundled before an expensive 
shortest path tree calculation and ip table update is started. <br>
The scheduled delay of a calculation is configurable via the attribute <code>spf_delay</code>.<br>
In combination with <code>spf_delay</code> there is the opportunity to configure a hold time 
between two consecutive spf calculations. This is done by setting the <code>spf_hold_time</code> 
attribute to an appropriate value (see section <b>Configuration</b> for further information).
The default value of <code>spf_hold_time</code> is <b>10 seconds</b>. <br> 
To start Routing Table calculation immediately after a topology change was realized, 
<code>spf_delay</code> and <code>spf_hold_time</code> must be both set to <b>0</b>!
</p>

<p>
As indicated before, spf calculation and Routing Table updates are quite time-consuming. 
According to a paper of Aman Shaikh <a href="#ref3">[3]</a> OSPFv2 v0.2.2 is able to model
the delays evoked by these actions. This is done as follows: When an spf calculation is up to
be executed, OSPFv2 first executes the algorithm, then waits for a certain amount of time (the 
calculation delay) and then prints debug information about the recalculated spf tree if 
configured. The calculation delay is computed according to <a href="#ref3">[3]</a> by the 
following formula:
<br><br>
<center><i>0.00000247 * x<sup>2</sup> + 0.000978 sec</i></center>
<br>
were <i>x</i> is the number of nodes in the network.<br>
Thereafter the <i>IP Forwarding Table</i> must be updated. First OSPFv2 waits a second 
amount of time before doing the updates and then installs and removes accordant routes
in the FIB of IP. Because <a href="#ref3">[3]</a> doesn't give exact answers to the
question how long an IP table update takes, the delay is modeled by a random value from
an interval of:
<br><br>
<center><i>100 to 300 milliseconds</i></center>
<br>
When updating the <i>IP Forwarding Table</i> OSPFv2 v0.2.2 only updates its own routes.
It also implements the interface <i>FIBChangeListener</i> to be notified when OSPFv2 routes
are changed or removed by other protocols. But at this time it does not react on changes.
</p>

<p>
A recency since OSPFv2 v0.2.1 is also the <code>Interface.PacingTimer</code>. With this new
timer it is now able to queue updated LSAs before they are flooded out in an 
<code>LS Update packet</code>. If there are LSAs left in the queue, the Timer fills and
sends out a packet in intervals of <b>0.033 seconds</b> until all LSAs are flooded, i.e.
the queue got empty. It is possible to configure the interval length by setting the
attribute <code>pacing_flood_time</code>. Please read the documentation of this attribute
carefully before using it. There are some restrictions on its values.
</p>

<a name="config"></a>
<h3>Configuration</h3>


<p align="justify">
Each individual OSPFv2 protocol session is configured separately. There are
only a few values which are mandatory. <a href="table1.html">
<code>Table 1</code></a> yields a specification of the sub-attributes of an 
OSPFv2 session, what there meaning is and which values are appropriate for
them. <br>
All interfaces on which OSPFv2 shall run have to be specified as sub-attributes
of an area, because each interface attaches the router to a certain area.
The areas again are configured as sub-attributes of the ProtocolSession. You
find a detailed description of the <i>area</i> sub-attributes in <a href=
"table2.html"><code>Table 2</code></a>. For details of how to configure the
sub-attributes of an <i>if</i> (OSPFv2 interface attribute) see <a href=
"table3.html"><code>Table 3</code></a>. A complete but short overview about
how to configure a whole session is given in the <a href="schema-excerpt.html">
<code>OSPFv2 Schema</code></a> and in <a href="../test/testexamples/">
<code>OSPFv2/test/testexamples/</code></a> you find some example configurations.
These examples aren't real validation tests. They represent simple networks in 
which basic features of OSPFv2 were tested. See <a href="#validation">Validation</a>
for more info about OSPFv2 testing.
</p>

<a name="compliance"></a>
<h3>Future Work</h3>


<p align="justify">
<b>1. Import of <i>static</i> and <i>host routes</i></b><br>
OSPFv2 version 0.2.2 distributes routing information about subnets only if it runs on at
least one interface connecting to those nets. Thereby it often sends routing information
into nets where these are superfluous (host nets). Also there is no possibility to 
distribute information about static routes to destinations outside the OSPFv2 routing
domain. To overcome this problem it should be possible to configure static and host routes 
on an OSPFv2 router.
</p>

<p align="justify">
<b>2. Support for <i>route aggregation</i> at area border routers</b><br>
Route aggregation is done on area border routers to reduce the amount of LSAs in link state
databases. This can only be done if address ranges are specified on these routers.
Therefore a new OSPFv2 attribute should be introduced and the OSPF code should be augmented 
to deal with it.
</p>

<p align="justify">
<b>3. Broadcast, Non-Broadcast Networks, Designated Router and Backup Designated Router</b><br>
OSPF is able to run on both, broadcast and non-broadcast networks. Version 0.2.2 in fact has 
rudimentary code to distinguish such networks, but it runs proper over point-to-point only. 
The parts in RFC 2328 <a href="#ref1">[1]</a> dealing with broadcast networks, (e.g. 
<i>Designated</i> and <i>Backup Designated Routers</i>) were not implemented because SSFNet IP 
does not support multicast.
</p>

<p align="justify">
<b>4. IP Multicast</b><br>
OSPFv2 version 0.2.2 can not rely on multicast. If IP Multicast will be available, unicast
must be replaced by it at several positions and the neighbor discovery process must be updated.
Refer to RFC 2328 <a href="#ref1">[1]</a> section 4.4.
</p>


<a name="src">
<h3>Source Code</h3>

<p>
Java source: <a href=".."><code>SSF/OS/OSPFv2/</code></a> [<a href="HISTORY">modification history</a>]<br>
</p>

<a name="validation"></a>
<h3>Validation</h3>

<p>
In parallel with the implementation of the protocol, a suite of validation tests for 
SSF.OS.OSPFv2 was developed at the Computer Networking Group at Saarland University 
and is available in <a href="../test/">OSPFv2/test/</a>. It consists of a subset of
tests from an existing test suite for OSPF conformance testing, provided by the
<a href="http://www.iol.unh.edu">InterOperability Lab</a> at the University of New 
Hampshire. <br>
Where needed, these tests were modified to accomplish the same tasks in the SSFNet 
environment as intended by the IOL. In addition, a few tests concerning Routing Table 
calculation were added.
</p>

<p>
With OSPFv2 v0.2.1 came a thoroughly revised and updated version of the test suite.
All former tests run proper and mirror the current state of the protocol's implementation.
Some additional tests have been sketched but they are not yet applicable. 
</p>

<p>
A detailed documentation of the OSPF test suite can be found <a href="../test/doc/index.html">here</a>. 
To perform the validation tests, change to directory OSPFv2/ and simply type 
<i>make testsuite</i> after OSPFv2 has been installed and compiled successfully.
</p>

<p>
To quickly verify the installation and to give some samples of how you may 
configure OSPFv2 in a simple network, there are some small test configurations
available in <a href="../test/testexamples">OSPFv2/test/testexamples/</a>.
Take a look in the <a href="../test/testexamples/README">README</a> for further
informations. To perform the tests, change to OSPFv2/ and type <i>make tests</i>. <br>
Since OSPFv2 version 0.2.0 there is a simple test scenario that shows how to configure 
and use an AS Boundary router and a stub area. See 
<a href="../test/testexamples/as_boundary">OSPFv2/test/testexamples/as_boundary/</a>
for more information.
</p>

<a name="references"></a>
<h3>References</h3>

<p>
<a name="ref1">
<font face="fixed">&nbsp;&nbsp;&nbsp;</font>[1]
<font face="fixed">&nbsp;</font><a href="http://www.ietf.cnri.reston.va.us/rfc/rfc2328.txt">RFC2328: OSPF Version 2</a><br>
</p>

<p>
<a name="ref2">
<font face="fixed">&nbsp;&nbsp;&nbsp;</font>[2]
<font face="fixed">&nbsp;</font><font color="blue"><i>Routing in the Internet</i></font> by Christian Huitema<br>
</p>

<p>
<a name="ref3">
<font face="fixed">&nbsp;&nbsp;&nbsp;</font>[3]
<font face="fixed">&nbsp;</font><a href="http://www.cse.ucsc.edu/~aman/publications.html">Experience in Black-box OSPF
Measurement</a> by Aman Shaikh and Albert Greenberg<br>
</p>

<a name="about"></a>
<h3>Authors</h3>

<p align="justify">
SSF.OS.OSPFv2 was originally authored by Hagen B&ouml;hm
&lt<a href="mailto: Hagen Boehm <hagen@net.uni-sb.de>">hagen@net.uni-sb.de</a>&gt
with advice from Dirk W. Jacob
&lt<a href="mailto: Dirk Jacob <dirk@d-jacob.net>">dirk@d-jacob.net</a>&gt
and Anja Feldmann
&lt<a href="mailto: Anja Feldmann <anja@net.uni-sb.de>">anja@net.uni-sb.de</a>&gt
. <br>
The validation tests were written and tested by Dirk Jacob. <br>
The design of the DML configuration schema for OSPFv2 was developed by Dirk Jacob and Anja 
Feldmann. <br>
Bugfixes due to failing validation tests were implemented by Hagen B&ouml;hm.
</p>

<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>
<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>
<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>
<br><br><br><br><br><br><br><br><br><br><br><br><br><br><br>

</body>
</html>
